home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_12_10 / allison / xref2.c < prev   
C/C++ Source or Header  |  1994-09-06  |  6KB  |  261 lines
  1. LISTING 9
  2. /* xref2.c: Cross-referencer with custom
  3.  *          memory management pools.
  4.  */
  5.  
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <string.h>
  9. #include <assert.h>
  10.  
  11. #define WORD_WIDTH 15
  12.  
  13. /* Linked-list structure for each list of line numbers */
  14. struct List
  15. {
  16.     int lnum;
  17.     struct List *next;
  18. };
  19. typedef struct List List;
  20.  
  21. /* Node structure for tree of distinct words */
  22. struct Tree
  23. {
  24.     char word[WORD_WIDTH];
  25.     List *lstptr;
  26.     struct Tree *left, *right;
  27. };
  28. typedef struct Tree Tree;
  29.  
  30. /* Binary search tree functions */
  31. Tree *addword(Tree *, char *);
  32. Tree *find_node(Tree *, char *);
  33. void print_tree(Tree *t);
  34. void init_tree_pool(void);  /* NEW */
  35. Tree *get_tree_node(void);  /* NEW */
  36. void free_tree_pool(void);  /* NEW */
  37.  
  38. /* Linked list functions */
  39. List *addline(List *, int);
  40. void print_list(List *);
  41. void init_list_pool(void);  /* NEW */
  42. List *get_list_node(void);  /* NEW */
  43. void free_list_pool(void);  /* NEW */
  44.  
  45. int  ndistinct = 0;
  46.  
  47.  
  48. main(int argc, char *argv[])
  49. {
  50.     char linebuf[BUFSIZ];
  51.     Tree *words = NULL;
  52.     int lineno = 0;
  53.  
  54.     /* Connect to optional input file */
  55.     if (argc > 1)
  56.         assert(freopen(argv[1],"r",stdin));
  57.  
  58.     /* NEW: Set-up memory pools */
  59.     init_tree_pool();
  60.     init_list_pool();
  61.  
  62.     /* Process each line of text file */
  63.     while (fgets(linebuf,BUFSIZ,stdin) != NULL)
  64.     {
  65.         char *wordptr, *lineptr = linebuf;
  66.         char *bad_chars = " \t\n\f\v\\\"~!@#$%^&*()+'"
  67.                           "|`1234567890-=\{}[]:;<>?,./";
  68.  
  69.         ++lineno;
  70.  
  71.         /* Process each word in line */
  72.         while ((wordptr = strtok(lineptr,bad_chars)) != NULL)
  73.         {
  74.             Tree *node;
  75.  
  76.             words = addword(words,wordptr);
  77.             node = find_node(words,wordptr);
  78.             node->lstptr = addline(node->lstptr,lineno);
  79.             lineptr = NULL;
  80.         }
  81.     }
  82.  
  83.     /* Print results */
  84.     printf("No. of distinct words: %d\n\n",ndistinct);
  85.     print_tree(words);
  86.  
  87.     /* Release pool memory */
  88.     free_list_pool();
  89.     free_tree_pool();
  90.     return 0;
  91. }
  92.  
  93. Tree *addword(Tree *tp, char *word)
  94. {
  95.     if (tp == NULL)
  96.     {
  97.         /* Add new entry */
  98.         ++ndistinct;
  99.         tp = get_tree_node();           /* CHANGED */
  100.         assert(tp);
  101.         strncpy(tp->word,word,WORD_WIDTH)[WORD_WIDTH] = '\0';
  102.         tp->left = tp->right = NULL;
  103.         tp->lstptr = NULL;
  104.     }
  105.     else if (strcmp(tp->word,word) < 0)
  106.         tp->right = addword(tp->right,word);
  107.     else if (strcmp(tp->word,word) > 0)
  108.         tp->left = addword(tp->left,word);
  109.  
  110.     return tp;
  111. }
  112.  
  113. List *addline(List *lp, int n)
  114. {
  115.     if (lp == NULL)
  116.     {
  117.         /* Append new line number to list */
  118.         List *newp = get_list_node();   /* CHANGED */
  119.         assert(newp);
  120.         newp->lnum = n;
  121.         newp->next = NULL;
  122.         return newp;
  123.     }
  124.     else if (lp->lnum != n)
  125.         lp->next = addline(lp->next,n);
  126.  
  127.     return lp;
  128. }
  129.  
  130. void print_tree(Tree *tp)
  131. {
  132.     if (tp != NULL)
  133.     {
  134.         /* Inorder traversal */
  135.         print_tree(tp->left);
  136.         printf("%-*.*s: ",WORD_WIDTH,WORD_WIDTH,tp->word);
  137.         print_list(tp->lstptr); putchar('\n');
  138.         print_tree(tp->right);
  139.     }
  140. }
  141.  
  142. void print_list(List *lp)
  143. {
  144.     const int NUM_WIDTH = 5;
  145.     const int INDENT = WORD_WIDTH + 2;
  146.     const int NUMS_PER_LINE = 8;
  147.     int count;
  148.  
  149.     for (count = 0; lp != NULL; lp = lp->next, ++count)
  150.     {
  151.         printf("%*d",NUM_WIDTH,lp->lnum);
  152.         if ((count+1) % NUMS_PER_LINE == 0
  153.              && lp->next != NULL)
  154.             printf("\n%*c",INDENT,' ');
  155.     }
  156. }
  157.  
  158. Tree *find_node(Tree *tp, char *s)
  159. {
  160.     /* Binary search for word */
  161.     if (strcmp(tp->word,s) > 0)
  162.         return find_node(tp->left,s);
  163.     else if (strcmp(tp->word,s) < 0)
  164.         return find_node(tp->right,s);
  165.     else
  166.         return tp;
  167. }
  168.  
  169. /*
  170.  * NEW: Pool management code follows
  171.  */
  172.  
  173. /* Tree Pool */
  174. typedef union Tree_shell
  175. {
  176.     union Tree_shell *next;
  177.     Tree dummy;
  178. } Tree_shell;
  179.  
  180. #define TREE_CHUNK 256
  181.  
  182. static Tree_shell *free_tree_ptr = NULL;
  183. static void *tree_pool = NULL;
  184.  
  185. void init_tree_pool(void)
  186. {
  187.     int i;
  188.  
  189.     /* Allocate pool of tree nodes */
  190.     tree_pool = calloc(TREE_CHUNK, sizeof(Tree));
  191.     assert(tree_pool);
  192.     free_tree_ptr = tree_pool;
  193.  
  194.     /* Link them together */
  195.     for (i = 0; i < TREE_CHUNK-1; ++i)
  196.         free_tree_ptr[i].next = &free_tree_ptr[i+1];
  197.     free_tree_ptr[TREE_CHUNK-1].next = NULL;
  198. }
  199.  
  200. Tree *get_tree_node(void)
  201. {
  202.     if (free_tree_ptr)
  203.     {
  204.         Tree *new_node = (Tree *) free_tree_ptr;
  205.         free_tree_ptr = free_tree_ptr->next;
  206.         return new_node;
  207.     }
  208.     else
  209.         return NULL;
  210. }
  211.  
  212. void free_tree_pool(void)
  213. {
  214.     free(tree_pool);
  215. }
  216.  
  217. /* List Pool */
  218. typedef union List_shell
  219. {
  220.     union List_shell *next;
  221.     List dummy;
  222. } List_shell;
  223.  
  224. #define LIST_CHUNK 1024
  225.  
  226. static List_shell *free_list_ptr = NULL;
  227. static void *list_pool = NULL;
  228.  
  229. void init_list_pool(void)
  230. {
  231.     int i;
  232.  
  233.     /* Allocate pool of List nodes */
  234.     list_pool = calloc(LIST_CHUNK, sizeof(List));
  235.     assert(list_pool);
  236.     free_list_ptr = list_pool;
  237.  
  238.     /* Link them together */
  239.     for (i = 0; i < LIST_CHUNK-1; ++i)
  240.         free_list_ptr[i].next = &free_list_ptr[i+1];
  241.     free_list_ptr[LIST_CHUNK-1].next = NULL;
  242. }
  243.  
  244. List *get_list_node(void)
  245. {
  246.     if (free_list_ptr)
  247.     {
  248.         List *new_node = (List *) free_list_ptr;
  249.         free_list_ptr = free_list_ptr->next;
  250.         return new_node;
  251.     }
  252.     else
  253.         return NULL;
  254. }
  255.  
  256. void free_list_pool(void)
  257. {
  258.     free(list_pool);
  259. }
  260.  
  261.